|
Earliest Deadline First(EDF)とは、リアルタイムオペレーティングシステムで使用される動的スケジューリング規則の一種である。プロセスは優先度つきキューに置かれる。スケジューリングイベントが発生すると(タスク終了、新規タスク生成など)、そのキューを探索して最も実行期限(デッドライン)が近いプロセスを選ぶ。そのプロセスが次に実行すべきものとしてスケジュールされる。 == 特徴 == 周期的に実行すべきプロセスのデッドラインはその周期に等しく、EDFによるCPU使用率の限界は100%である。すなわちEDFはCPU使用率の合計が100%を超えない限り全てのデッドラインを守ることを保証できる。従って、レートモノトニックスケジューリングのような固定優先度スケジューリングに比較して、EDFはより高負荷な環境でも全てのデッドラインを守ることができる。 しかし、システムが過負荷状態のとき、デッドラインを守れなくなるプロセスを予測できない(デッドラインと過負荷の発生時刻に依存する)。この欠点はリアルタイムシステム設計においては重大である。またこのアルゴリズムを実装するのも難しく、デッドラインを数バイトで表すにはやや技巧を必要とする(デッドラインは数ミリ秒かもしれないし数百分かもしれない)。このため、EDFは実際の産業用リアルタイムシステムではあまり使われない。 EDFスケジューリングに関しては多くの研究がなされている。EDFでプロセスの応答時間の最悪ケースを計算することができ、周期的プロセス以外にも適用可能である。ただし、マルチプロセッシングシステムではEDFはうまく機能しない。 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「Earliest Deadline First」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Earliest deadline first scheduling 」があります。 スポンサード リンク
|